﻿namespace LeetCode_Learn
{
    public class Part06_BSOneLeftNear
    {
        public static int Get(int[] arr, int num)
        {
            if (arr == null)
                throw new ArgumentNullException("arr不可为空!");
            if (arr.Length < 2)
                return arr[0];

            return binary(arr, 0, arr.Length - 1, num);
        }

        public static int binary(int[] arr, int left, int right, int num)
        {
            if (left > right)//递归结束
                return -1;
            int mid = (left + right) / 2;
            int midVal = arr[mid];
            //如果当前中间值>=num且左边元素也>=num,则向左递归
            if (mid - 1 >= 0 && midVal >= num && arr[mid - 1] >= num)
                return binary(arr, left, mid - 1, num);//向左递归
                                                       //如果当前中间值>=num但左边元素<num,则直接返回该中间值
            else if (mid - 1 >= 0 && midVal >= num && arr[mid - 1] < num)
                return mid;
            //其他情况向右递归
            else
                return binary(arr, mid + 1, right, num);//向右递归
        }

    }
}
